The problem can be found at the following link: Question Link
To reverse the given equation, I have used the following approach:
- I utilized two stacks:
num
to store the numbers andop
to store the operators encountered. - I iterated through the given string
str
character by character. - If the current character
i
is not a digit (i.e., an operator), I pushed the accumulated strings
(which represents a number) into thenum
stack and pushed the operatori
into theop
stack. Then, I resets
to an empty string. - If the current character
i
is a digit, I appended it to the strings
. - After processing all the characters, I pushed the remaining accumulated string
s
into thenum
stack. - Next, I initialized an empty string
s
to store the reversed equation. - While the
op
stack is not empty, I popped the top element from both thenum
andop
stacks. I appended the popped number and operator alternately to the strings
. - Finally, I appended the remaining number from the
num
stack to the strings
. - I returned the reversed equation string
s
.
- Time Complexity:
O(N)
, whereN
is the length of the given stringstr
. The algorithm iterates through each character ofstr
once. - Space Complexity:
O(N)
, whereN
is the length of the given stringstr
. This is because the algorithm uses two stacks to store the numbers and operators encountered.
class Solution
{
public:
string reverseEqn (string str)
{
stack<string> num;
stack<char> op;
string s = "";
for(auto i: str){
if(i<'0' || i>'9'){
num.push(s);
op.push(i);
s = "";
}
else
s += i;
}
num.push(s);
s = "";
while(!op.empty()){
s += num.top();
s += op.top();
num.pop();
op.pop();
}
s += num.top();
return s;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star
to the getlost01/gfg-potd repository.